The present invention relates to the field of communication networks, and, more particularly, to mobile ad hoc wireless networks and related methods.
Wireless networks have experienced increased development in the past decade. One of the most rapidly developing areas is mobile ad hoc networks. Physically, a mobile ad hoc network includes a number of geographically-distributed, potentially mobile nodes wirelessly connected by one or more radio frequency channels. Compared with other type of networks, such as cellular networks or satellite networks, the most distinctive feature of mobile ad hoc networks is the lack of any fixed infrastructure. The network is formed of mobile nodes only, and a network is created on the fly as the nodes transmit to or receive from other nodes. The network does not in general depend on a particular node and dynamically adjusts as some nodes join or others leave the network.
In a hostile environment where a fixed communication infrastructure is unreliable or unavailable, such as in a battle field or in a natural disaster area struck by earthquake or hurricane, an ad hoc network can be quickly deployed and provide much needed communications. While the military is still a major driving force behind the development of these networks, ad hoc networks are quickly finding new applications in civilian or commercial areas. Ad hoc networks will allow people to exchange data in the field or in a class room without using any network structure except the one they create by simply turning on their computers or PDAs.
As wireless communication increasingly permeates everyday life, new applications for mobile ad hoc networks will continue to emerge and become an important part of the communication structure. Mobile ad hoc networks pose serious challenges to the designers. Due to the lack of a fixed infrastructure, nodes must self-organize and reconfigure as they move, join or leave the network. All nodes could potentially be functionally identical and there may not be any natural hierarchy or central controller in the network. Many network-controlling functions are distributed among the nodes. Nodes are often powered by batteries and have limited communication and computation capabilities. The bandwidth of the system is usually limited. The distance between two nodes often exceeds the radio transmission range, and a transmission has to be relayed by other nodes before reaching its destination. Consequently, a network has a multihop topology, and this topology changes as the nodes move around.
The Mobile Ad-Hoc Networks (MANET) working group of the Internet Engineering Task Force (IETF) has been actively evaluating and standardizing routing, including multicasting, protocols. Because the network topology changes arbitrarily as the nodes move, information is subject to becoming obsolete, and different nodes often have different views of the network, both in time (information may be outdated at some nodes but current at others) and in space (a node may only know the network topology in its neighborhood usually not far away from itself).
A routing protocol needs to adapt to frequent topology changes and with less accurate information. Because of these unique requirements, routing in these networks is very different from others. Gathering fresh information about the entire network is often costly and impractical. Many routing protocols are reactive (on-demand) protocols: they collect routing information only when necessary and to destinations they need routes to, and do not generally maintain unused routes after some period of time. This way the routing overhead is greatly reduced compared to pro-active protocols which maintain routes to all destinations at all times. It is important for a protocol to be adaptive. Ad Hoc on Demand Distance Vector (AODV), Dynamic Source Routing (DSR) and Temporally Ordered Routing Algorithm (TORA) are representative of on-demand routing protocols presented at the MANET working group.
Examples of other various routing protocols include Destination-Sequenced Distance Vector (DSDV) routing which is disclosed in U.S. Pat. No. 5,412,654 to Perkins, and Zone Routing Protocol (ZRP) which is disclosed in U.S. Pat. No. 6,304,556 to Haas. ZRP is a hybrid protocol using both proactive and reactive approaches based upon distance from a source node.
These conventional routing protocols use a best effort approach in selecting a route from the source node to the destination node. Typically, the number of hops is the main criteria (metric) in such a best effort approach. In other words, the route with the least amount of hops is selected as the transmission route.
In view of the foregoing background, it is therefore an object of the present invention to provide the management and control of route discovery and associated processes via temporal transitioning processes and events in a mobile ad hoc network. For the present invention, it is to be understood that when a route discovery process is switched, so are its associated processes which include, for example, route maintenance.
This and other objects, features, and advantages in accordance with the present invention are provided by a method for managing and controlling the discovery and maintenance of routes in a mobile ad hoc network. The network includes a plurality of wireless mobile nodes and a plurality of wireless communication links connecting the nodes together. The method includes building and updating route tables at each node with a first one of proactive and reactive route discovery processes to define routes in the network. A route is a set of links and nodes from a source to a destination. The method also includes collecting and storing route stability information (statistics, heuristic rules, inferences, etc.) at each node, predicting route stability over time based upon the route stability information, and switching to a second one of the proactive and reactive route discovery processes when predicted route stability reaches a first transition parameter. Moreover, the method preferably includes switching back to the first one of the proactive and reactive route discovery processes when predicted route stability reaches a second transition parameter. The method manages and controls route maintenance processes even if they are identical for both the proactive and reactive cases.
The first and second transition parameters preferably comprise time-dependent thresholds, for example thresholds based upon a rate of change of source-destination subset pairs for at least one source node. The source-destination subset pairs comprise subsets of possible destination nodes for a designated source node. The time-dependent route stability information may be based upon node mobility, link failure, link creation, traffic congestion, any Quality of Service metric or any other parameter which is time dependent.
Furthermore, collecting and storing route stability information may include creating and updating a time-dependent route stability profile and/or a time-dependent route segment stability profile. A route segment is a set of links and nodes which define a reusable entity in each of a plurality of routes. Switching route discovery processes may also based upon the amount of nodes in the network, and may comprise multicasting a process-switch message to affected nodes of the network. Such affected nodes may be all the network nodes or a subset of the network nodes.
A system aspect of the invention is directed to a mobile ad hoc network having a plurality of wireless mobile nodes, and a plurality of wireless communication links connecting the nodes together. Each mobile node comprises a communications device to wirelessly communicate with other nodes of the plurality of nodes via the wireless communication links, and a controller to route communications via the communications device. The controller includes route tables defining routes in the network, wherein a route is defined by a set of links and nodes from a source to a destination. The controller also includes a route discovery module to discover routes and update the route tables with one of a plurality of route discovery processes, e.g. proactive and a reactive route discovery processes, a stability profile memory to store route stability information, a route stability predictor to predict route stability over time based upon the route stability information, a route discovery process selector to select between the proactive and reactive route discovery processes based upon the predicted route stability, a route maintenance process associated with the proactive route discovery process, and a route maintenance process associated with the reactive route discovery process. The route maintenance process for both the reactive and proactive route discovery processes may be identical.